class Solution {
    string aim;
    int m, n;
    vector<vector<bool>> vis;

public:
    bool exist(vector<vector<char>>& board, string word) {
        aim = word;
        m = board.size(), n = board[0].size();
        vis = vector<vector<bool>>(m, vector<bool>(n, false));

        unordered_map<char, int> cnt;
        for (auto& row : board) {
            for (char c : row) {
                cnt[c]++;
            }
        }

        // 优化一
        unordered_map<char, int> word_cnt;
        for (char c : word) {
            if (++word_cnt[c] > cnt[c]) {
                return false;
            }
        }

        // 优化二
        if (cnt[word.back()] < cnt[word[0]]) {
            ranges::reverse(aim);
        }

        // 枚举所有起点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == aim[0]) {
                    if (dfs(board, i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    bool dfs(vector<vector<char>>& board, int i, int j, int k) {
        if (board[i][j] != aim[k]) { // 匹配失败
            return false;
        }

        if (k + 1 == aim.size()) {
            return true;
        }
        // 标记当前位置为已访问
        vis[i][j] = true;

        for (int d = 0; d < 4; d++) {
            int x = i + dx[d];
            int y = j + dy[d];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
                dfs(board, x, y, k + 1)) {
                return true;
            }
        }
        // 回溯：恢复访问状态
        vis[i][j] = false;
        return false;
    }
};

